Related Work
Our new cryptosystem will be referred to as TST from the initials of the first names of the inventors. TST is theoretically related to, yet dramatically different from cryptosystem PGM which is, to our knowledge, the only cryptosystem based on factorizations of arbitrary non-abelian permutation groups.
Private key cryptosystem PGM was invented by S. Magliveras in the late 1970's. The system was described in his paper titled "A cryptosystem from logarithmic signatures of finite groups", Proceedings of the 29th Midwest Symposium on Circuits and Systems, Elsevier Publishing Company (1986), pp 972-975. An earlier paper by S. S. Magliveras, B. A. Oberg and A. J. Surkan, titled "A New Random Number Generator from Permutation Groups", Rend. del Sem. Matemat. e Fis. di Milano, LIV (1984), pp 203-223 also discusses PGM. The statistical and algebraic properties of PGM were studied by S. S. Magliveras and N. D. Memon in their papers "Algebraic Properties of Cryptosystem PGM", Journal of Cryptology, 5 (1992), pp 167-183, and "The Linear Complexity Profile of Cryptosystem PGM", Congressus Numerantium, Utilitas Mathematica, 72 (1989), pp 51-60. Additional related work appeared in the papers: "Complexity tests for cryptosystem PGM, Congressus Numerantium, Utilitas Mathematica, 79 (1990). pp 61-68, by S. S. Magliveras, N. D. Memon and K. C. Tam, and in "Factorizations of elementary Abelian p-groups and their cryptographic significance", J. of Cryptology, 7 (1994), pp 201-212 by M. Qu and S. A. Vanstone. Here we include only a brief description of PGM.
PGM is based on certain fundamental data structures for permutation groups, which are called logarithmic signatures. Let G be a permutation group of degree n. A logarithmic signature for G is an ordered collection .alpha.=(A.sub.0, A.sub.1 , . . . , A.sub.w-1) of ordered subsets A.sub.i =(a.sub.i,0 , . . . , a.sub.i,r.sbsb.i.sub.-1) of G, such that each element g .epsilon. G has a unique representation as a product of the form EQU g=a.sub.0,x.sbsb.0 .multidot.a.sub.1,x.sbsb.1 . . . a.sub.w-1,x.sbsb.w-1 a.sub.i,x.sbsb.i .epsilon. A.sub.i (1)
Thus, g corresponds to a unique vector x=(x.sub.0, . . . , x.sub.w-1), where 0.ltoreq.x.sub.i .ltoreq.r.sub.i =.vertline.A.sub.i .vertline.. The property that (A.sub.0 , . . . , A.sub.w-1) is a logarithmic signature can best be described by means of the equation: EQU G=A.sub.0 . . . A.sub.w-2 .multidot.A.sub.w-1 (2)
holding in the group ring G. It is a necessary condition for cryptographic security that the order of G be exponential in n, while for computational efficiency it is necessary that ##EQU1## be bounded by a polynomial in n.
The A.sub.i are called the blocks of .alpha., the vector of block lengths r=(r.sub.0, . . . , r.sub.w-1) is called the type of .alpha., and ##EQU2## is called the length of .alpha.. There are tame logarithmic signatures i.e. those for which the factorization for each g can be obtained in time polynomial in n, supertame signatures (the factorization can be obtained in time O(n.sup.2)) and there are wild signatures for which the factorization requires time O(.vertline.G.vertline.). The question of existence of tame logarithmic signatures has been settled. It has been shown that each member of an extremely large class of signatures is tame. This is the class of so called transversal logarithmic signatures. There exist an even larger number of non-transversal logarithmic signatures (see "On Logarithmic Signatures and Applications", M. Sc. Thesis, University of Nebraska--Lincoln, (1989), pp 1-59), but the question of whether the class of non-transversal logarithmic signatures is identical with the class of wild signatures is open and appears to be equivalent to the complexity-theory question P.noteq.NP. Surprisingly, the smallest group which has non-transversal logarithmic signatures is the cyclic group .sub.8. Let .LAMBDA.=.LAMBDA.(G) denote the family of all logarithmic signatures of a given group G.
Each signature .alpha. .epsilon. .LAMBDA. of type (r.sub.0, . . . , r.sub.w-1) induces a bijection .alpha.:.sub..vertline.G.vertline. (.apprxeq..sub.r.sbsb.0 .sym. . . . .sym..sub.r.sbsb.w-1).fwdarw.G, which is efficiently invertible if and only if .alpha. is tame.
To understand some of the significant differences between TST and PGM it is important to describe the mapping .alpha. mentioned above. If .alpha.=(A.sub.0, . . . , A.sub.w-1) is a logarithmic signature for G, we denote by .alpha..sub.ij the j.sup.th element of block A.sub.i of .alpha.. Let r=(r.sub.0, . . . , r.sub.w-1) be the type of .alpha.. We now define a bijection .THETA..sub..alpha. : .sub.r.sbsb.0 .sym. . . . .sym. .sub.r.sbsb.w-1 .fwdarw.G by: EQU .THETA..sub..alpha. (x.sub.0, . . . , x.sub.w-1)=.alpha..sub.0,x.sbsb.0 .multidot..alpha..sub.1,x.sbsb.1 . . . .alpha..sub.w-1,x.sbsb.w-1(3)
Next, define the integers m.sub.i, i=0, 1, . . ., w-1 by ##EQU3## and let .lambda. be the bijection from .sub.r.sbsb.0 .sym. . . . .sym. .sub.r.sbsb.w-1 onto .sub..vertline.G.vertline., defined by ##EQU4## For any x .epsilon. .sub..vertline.G.vertline., .lambda..sup.-1 (x) is efficiently computable by successive subtractions. This corresponds to obtaining the mixed base representation of x with respect to (r.sub.0, . . . , r.sub.w-1). Next, for any .alpha. .epsilon. .LAMBDA., define a map .alpha.: .sub..vertline.G.vertline. .fwdarw.G by composing .lambda..sup.-1 with .THETA..sub..alpha., thus .alpha.=.lambda..sup.-1 .THETA..sub..alpha.. FIG. 5. illustrates the definition of .alpha..
The .lambda..sup.-1 or .lambda. portions in computing .alpha.=.lambda..sup.-1 .THETA..sub..alpha., or .alpha..sup.-1 =.THETA..sub..alpha..sup.-1 .lambda. are referred to as knapsack segments.
The function .alpha. is always efficiently computable, but .alpha..sup.-1 is not unless .alpha. is tame. We denote by .LAMBDA. the collection {.alpha.:.alpha. .epsilon. .LAMBDA.}.
Basic PGM uses a pair of tame logarithmic signatures (.alpha.,.beta.) and defines the encryption transformation as the mapping E.sub..alpha.,.beta. =.alpha. .beta..sup.-1 :.sub..vertline.G.vertline. .fwdarw..sub..vertline.G.vertline. and the corresponding decryption transformation as D.sub..alpha.,.beta. =E.sub..beta.,.alpha. =.beta. .alpha..sup.-1.
We illustrate basic PGM by means of a small example. The group used is the alternating group on five points, A.sub.5, of order 60. This implies that the message space is the set .sub.60 ={0, 1, . . . , 59}. Consider below a table consisting of two log signatures .alpha. and .beta. for A.sub.5. For simplicity we have selected both .alpha. and .beta. to be of type (5,4,3). For compatibility reasons with the new TST system we list the blocks of a logarithmic signature .alpha.=(A.sub.0, . . . , A.sub.w-1) so that the A.sub.i are stacked sequentially one on top of the other with A.sub.0 at the bottom and A.sub.w-1 at the top. The central column of the table displays the common knapsack vector v to be used in the knapsack segments of the encrypting and decrypting functions. The integers m.sub.i are 1, 5 and 20 respectively. Let us now demonstrate the operation of enciphering. If for example, the plaintext message is 56, it can be uniquely decomposed with respect to v as, 56=(1+15+40)=1.multidot.m.sub.0 +3.multidot.m.sub.1 +2.multidot.m.sub.2. This determines uniquely the vector of row-indices .lambda..sup.-1 (56)=(1,3,2). We next compute EQU .pi.=.THETA..sub..alpha. (1,3,2)=(1 5 4 3 2).multidot.(1)(2 4)(3 5).multidot.(1)(2)(3 5 4)=(1 5 2)(3)(4).
We then compute .THETA..sub..beta..sup.-1 (.pi.), that is the representation of .pi. with respect to .beta.. Because .beta. is supertame the factorization can be obtained very efficiently but we will not go into this process here. After the factorization has been achieved we have EQU .pi.=(1 5 2)(3)(4)=(1 3 5 4 2).multidot.(1)(2 3 4)(5).multidot.(1)(2)(3 4 5 )
This determines the indices for .beta. as (3,1,0), i.e. EQU .THETA..sub..beta..sup.-1 (.pi.)=(3,1,0)
Finally, .lambda.(3, 1, 0)=3+5+0=8. Hence, E.sub..alpha.,.beta. (56)=8. It can be easily verified now that D.sub..alpha.,.beta. (8)=E.sub..beta.,.alpha. (8)=56.
______________________________________ .alpha. v .beta. ______________________________________ (1)(2)(3)(4)(5) 0 (1)(2)(3 4 5) (1)(2)(3 4 5) 20 (1)(2)(3 5 4) (1)(2)(3 5 4) 40 (1)(2)(3)(4)(5) (1)(2)(3)(4)(5) 0 (1)(2 5)(3 4) (1)(2 3)(4 5) 5 (1)(2 3 4)(5) (1)(2 5)(3 4) 10 (1)(2 4 3)(5) (1)(2 4)(3 5) 15 (1)(2)(3 4 5) (1)(2)(3)(4)(5) 0 (1 4 2 3 5) (1 5 4 3 2) 1 (1)(2)(3 5 4) (1 3 5 2 4) 2 (1 2 5 4 3) (1 2 3 4 5) 3 (1 3 5 4 2) (1 4 2 5 3) 4 (1 5 4)(2)(3) ______________________________________
Some of the aforementioned references describe methods for obtaining pseudorandom logarithmic signatures from a very large class of transversal signatures and we will not go into this description either.
A hardware implementation for PGM was proposed by T. Horvath, S. Magliveras and Tran van Trung in "A Parallel Permutation Multiplier for a PGM Cryptochip", Advances in Cryptology--CRYPTO'94, Springer-Verlag 1994, pp 108-113. The proposed implementation adheres heavily to the ideas involved in the initial PGM including the knapsack portions at the front and back end of the encryption and decryption transformations.